{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Gas Station"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canCompleteCircuit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #加油站"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一条环路上有 <code>n</code>&nbsp;个加油站，其中第 <code>i</code>&nbsp;个加油站有汽油&nbsp;<code>gas[i]</code><em>&nbsp;</em>升。</p>\n",
    "\n",
    "<p>你有一辆油箱容量无限的的汽车，从第<em> </em><code>i</code><em> </em>个加油站开往第<em> </em><code>i+1</code><em>&nbsp;</em>个加油站需要消耗汽油&nbsp;<code>cost[i]</code><em>&nbsp;</em>升。你从其中的一个加油站出发，开始时油箱为空。</p>\n",
    "\n",
    "<p>给定两个整数数组 <code>gas</code> 和 <code>cost</code> ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 <code>-1</code> 。如果存在解，则 <strong>保证</strong> 它是 <strong>唯一</strong> 的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> gas = [1,2,3,4,5], cost = [3,4,5,1,2]\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:\n",
    "</strong>从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油\n",
    "开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油\n",
    "开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油\n",
    "开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油\n",
    "开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油\n",
    "开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。\n",
    "因此，3 可为起始索引。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> gas = [2,3,4], cost = [3,4,3]\n",
    "<strong>输出:</strong> -1\n",
    "<strong>解释:\n",
    "</strong>你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。\n",
    "我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油\n",
    "开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油\n",
    "开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油\n",
    "你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。\n",
    "因此，无论怎样，你都不可能绕环路行驶一周。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>gas.length == n</code></li>\n",
    "\t<li><code>cost.length == n</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= gas[i], cost[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [gas-station](https://leetcode.cn/problems/gas-station/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [gas-station](https://leetcode.cn/problems/gas-station/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]\\n[3,4,5,1,2]', '[2,3,4]\\n[3,4,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        if sum(gas) < sum(cost):\n",
    "            return -1\n",
    "        total, res = 0, 0\n",
    "        for i in range(len(gas)):\n",
    "            total += (gas[i] - cost[i])\n",
    "            if total < 0:\n",
    "                total = 0\n",
    "                res = i + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas, cost):\n",
    "        \"\"\"\n",
    "        :type gas: List[int]\n",
    "        :type cost: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(gas)\n",
    "        for i in range(n):\n",
    "            gas[i] -= cost[i]\n",
    "        total = 0\n",
    "        partial = 0\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            total += gas[i]\n",
    "            partial += gas[i]\n",
    "            if partial < 0:\n",
    "                s = i + 1\n",
    "                partial = 0\n",
    "        if total < 0:\n",
    "            return -1\n",
    "        else:\n",
    "            return s\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas, cost):\n",
    "        \"\"\"\n",
    "        :type gas: List[int]\n",
    "        :type cost: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        totalGas=sum(gas)\n",
    "        totalCost=sum(cost)\n",
    "\n",
    "        if totalCost>totalGas:\n",
    "           return -1\n",
    "\n",
    "        for i in range(len(gas)):\n",
    "            if gas[i] >= cost[i]:\n",
    "                tmpIndex=i\n",
    "                gasPlus=0\n",
    "                for j in range(len(gas)):\n",
    "                    gasPlus+= (gas[tmpIndex]-cost[tmpIndex])\n",
    "                    if gasPlus<0 :\n",
    "                        break\n",
    "                    tmpIndex += 1\n",
    "                    if tmpIndex == len(gas):\n",
    "                        tmpIndex=0\n",
    "                if tmpIndex == i:\n",
    "                    return tmpIndex\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas, cost):\n",
    "        \"\"\"\n",
    "        :type gas: List[int]\n",
    "        :type cost: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 思路链接: https://www.cnblogs.com/boring09/p/4248482.html\n",
    "        # Great Solution 1: 基于数学定理\n",
    "        # 如果一个数组的总和非负，那么一定可以找到一个起始位置，从他开始绕数组一圈，累加和一直都是非负的\n",
    "        # 求取开始位置只需要关注在哪个为止开始之后到某一位置油耗不满足跑完剩下路程，则应该从j+1位置开始\n",
    "#         start = 0\n",
    "#         remain = 0\n",
    "#         dept = 0\n",
    "        \n",
    "#         for i in range(len(gas)):\n",
    "#             remain += gas[i] - cost[i]\n",
    "#             if remain < 0:\n",
    "#                 dept += remain \n",
    "#                 start = i + 1\n",
    "#                 remain = 0\n",
    "#         return (start if remain + dept >= 0 else -1)\n",
    "    \n",
    "        # Solution: DP\n",
    "        # https://leetcode.com/problems/gas-station/discuss/206911/Python-beats-100-with-explanation-and-plots\n",
    "        n = len(gas)\n",
    "        dp = [gas[0] - cost[0]]\n",
    "        for i in range(1, n):\n",
    "            dp.append(dp[-1] + gas[i] - cost[i])\n",
    "        if dp[-1] < 0:\n",
    "            return -1\n",
    "        return (dp.index(min(dp)) + 1) % n\n",
    "        \n",
    "\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: 'List[int]', cost: 'List[int]') -> 'int':\n",
    "        length=len(gas)\n",
    "        \n",
    "        for i in range(length):\n",
    "            rest=0\n",
    "            for j in range(length):\n",
    "                cur=(i+j)%length\n",
    "                rest+=(gas[cur]-cost[cur])\n",
    "                \n",
    "                if rest<0:\n",
    "                    break\n",
    "                 \n",
    "            if rest>=0:\n",
    "                return i\n",
    "            \n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import operator\n",
    "# map(operator.add, first,second)\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas, cost):\n",
    "        \"\"\"\n",
    "        :type gas: List[int]\n",
    "        :type cost: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        above0={}\n",
    "        newlist=list(map(operator.sub,gas,cost))\n",
    "        # print(newlist)      \n",
    "        for i in range(0,len(newlist)):\n",
    "            if newlist[i]<0:\n",
    "                continue\n",
    "            else:\n",
    "                above0[i]=newlist[i]\n",
    "        for j in above0:\n",
    "            sumcost=newlist[j]\n",
    "            for i in range(1,len(newlist)):\n",
    "                if j+i>len(newlist)-1:\n",
    "                    sumcost=sumcost+newlist[(j+i)-len(newlist)]\n",
    "                else:\n",
    "                    sumcost=sumcost+newlist[j+i]\n",
    "                if sumcost<0:\n",
    "                    break\n",
    "            else:\n",
    "                return j\n",
    "        else:\n",
    "            return -1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import operator\n",
    "# map(operator.add, first,second)\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas, cost):\n",
    "        \"\"\"\n",
    "        :type gas: List[int]\n",
    "        :type cost: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        above0={}\n",
    "        newlist=list(map(operator.sub,gas,cost))\n",
    "        # print(newlist)      \n",
    "        for i in range(0,len(newlist)):\n",
    "            if newlist[i]<0:\n",
    "                continue\n",
    "            else:\n",
    "                above0[i]=newlist[i]\n",
    "        print(above0)\n",
    "        for j in above0:\n",
    "            # print(j)\n",
    "            sumcost=newlist[j]\n",
    "            for i in range(1,len(newlist)):\n",
    "                # print(above0[j]+i)\n",
    "                if j+i>len(newlist)-1:\n",
    "                    # print((above0[j]+i)-len(newlist))\n",
    "                    sumcost=sumcost+newlist[(j+i)-len(newlist)]\n",
    "                else:\n",
    "                    sumcost=sumcost+newlist[j+i]\n",
    "                if sumcost<0:\n",
    "                    break\n",
    "            else:\n",
    "                return j\n",
    "        else:\n",
    "            return -1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas, cost):\n",
    "        \"\"\"\n",
    "        :type gas: List[int]\n",
    "        :type cost: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        gap = []\n",
    "        for i in range(len(gas)):\n",
    "            gap.append(gas[i] - cost[i])\n",
    "        if sum(gap) < 0: return -1\n",
    "        sum_gap = [gap[0]]\n",
    "        for i in range(1, len(gap)):\n",
    "            sum_gap.append(gap[i] + sum_gap[-1])\n",
    "        return (sum_gap.index(min(sum_gap)) + 1) % len(gas)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas, cost):\n",
    "        \"\"\"\n",
    "        :type gas: List[int]\n",
    "        :type cost: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(gas)\n",
    "        a=[0]*n\n",
    "        for i in range(n):\n",
    "            a[i]=gas[i]-cost[i]\n",
    "        a=[0]+a*2\n",
    "        # print(a)\n",
    "        sum=[0]*(2*n+1)  #方便求环\n",
    "        for i in range(1,n*2+1):\n",
    "            sum[i]=sum[i-1]+a[i] \n",
    "        for i in range(1,n+1):\n",
    "            if (a[i]>=0) and (a[i-1]<=0):\n",
    "                flag=True\n",
    "                for j in range(n):\n",
    "                    # print(sum[i-1],sum[i+j],sum[i+j]-sum[i-1])\n",
    "                    if flag and (sum[i+j]-sum[i-1]<0):\n",
    "                        flag=False\n",
    "                if flag:\n",
    "                    return i-1\n",
    "        # print(sum)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: 'List[int]', cost: 'List[int]') -> 'int':\n",
    "        if not len(gas) or not len(cost) or len(gas) != len(cost): return -1\n",
    "        \n",
    "        tank = 0\n",
    "        total = 0\n",
    "        start = 0\n",
    "        \n",
    "        for i in range(len(gas)):\n",
    "            tank += gas[i] - cost[i]\n",
    "            \n",
    "            if tank < 0:\n",
    "                start = i + 1\n",
    "                total += tank\n",
    "                tank = 0\n",
    "        \n",
    "        if total + tank < 0: return -1\n",
    "        else: return start"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        n = len(gas)\n",
    "        g = []\n",
    "        for i in range(n):\n",
    "            g.append(gas[i] - cost[i])\n",
    "        for j in range(n):\n",
    "            s = 0\n",
    "            if g[j] < 0:\n",
    "                continue\n",
    "            else:\n",
    "                s += g[j]\n",
    "                for k in range(j+1, n):\n",
    "                    s += g[k]\n",
    "                    if s < 0:\n",
    "                        break\n",
    "                if s < 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    for l in range(j):\n",
    "                        s += g[l]\n",
    "                        if s < 0:\n",
    "                            break\n",
    "                    if s >= 0:\n",
    "                        return j\n",
    "        return -1\n",
    "                            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        length = len(gas)\n",
    "\n",
    "        for i in range(length):\n",
    "            sp = 0\n",
    "            si = i\n",
    "            sp += gas[i]\n",
    "            sp -= cost[i]\n",
    "            if sp < 0:\n",
    "                continue\n",
    "            while (si + 1) % length != i:\n",
    "                si = (si + 1) % length\n",
    "                sp += gas[si]\n",
    "                sp -= cost[si]\n",
    "                if sp < 0:\n",
    "                    break\n",
    "            else:\n",
    "                return i\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:  \n",
    "#         n=len(gas)\n",
    "#         for i in range(n):\n",
    "#             oil=gas[i]-cost[i]\n",
    "#             ii=i\n",
    "#             while oil>=0:\n",
    "#                 if ii==n-1:\n",
    "#                     ii=0\n",
    "#                 else:ii+=1\n",
    "#                 if ii==i:return i\n",
    "#                 oil=oil+gas[ii]-cost[ii]\n",
    "#         return -1\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        # total记录可获得的总油量-总油耗， cur记录当前油耗情况， ans记录出发位置\n",
    "        total, cur, ans = 0, 0, 0\n",
    "        for i in range(len(gas)):\n",
    "            total += gas[i] - cost[i]\n",
    "            cur += gas[i] - cost[i]\n",
    "            if cur < 0:                     # 油不够开到i站\n",
    "                cur = 0                     # cur置零，在新位置重新开始计算油耗情况\n",
    "                ans = i + 1                 # 将起始位置改成i+1\n",
    "        return ans if total >= 0 else -1    # 如果获得的汽油的量小于总油耗，则无法环\n",
    "                                            # 行一周返回 -1；反之返回ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\r\n",
    "        total, cur, ans = 0, 0, 0\r\n",
    "        for i in range(len(gas)):\r\n",
    "            total += gas[i] - cost[i]\r\n",
    "            cur += gas[i] - cost[i]\r\n",
    "            if cur < 0:\r\n",
    "                cur = 0\r\n",
    "                ans = i + 1\r\n",
    "        return ans if total >= 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        n = len(gas)\n",
    "        for i in range(n):\n",
    "            has_gas = 0\n",
    "            for g, c in zip(gas[i:]+gas[:i], cost[i:]+cost[:i]):\n",
    "                has_gas = has_gas + g - c\n",
    "                if has_gas < 0:\n",
    "                    break\n",
    "            else:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        diff = [i - j for i, j in zip(gas, cost)]\n",
    "        min_value = float(\"inf\")\n",
    "        min_index = 0\n",
    "       \n",
    "        tmp = 0\n",
    "        for ix, val in enumerate(diff):\n",
    "            tmp += val\n",
    "            if tmp < min_value:\n",
    "                min_index = ix\n",
    "                min_value = tmp\n",
    "        \n",
    "        if tmp < 0:\n",
    "            return -1\n",
    "        return (min_index + 1) % len(gas)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        # diff = []\n",
    "        # size = len(gas)\n",
    "        # for i in range(size):\n",
    "        #     diff.append(gas[i] - cost[i])\n",
    "        \n",
    "        # start = -1\n",
    "        # for i in range(size)\n",
    "\n",
    "        size = len(gas)\n",
    "        for i in range(size):\n",
    "            if gas[i] < cost[i]:\n",
    "                continue\n",
    "            else:\n",
    "                sign = True\n",
    "                capacity = 0\n",
    "                for j in range(i, size + i):\n",
    "                    index = j if j < size - 1 else j - size\n",
    "                    capacity = capacity + gas[index] - cost[index]\n",
    "                    if capacity < 0:\n",
    "                        sign = False\n",
    "                        break\n",
    "                if sign:\n",
    "                    return i\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        n=len(gas)\n",
    "        g=gas\n",
    "        g[0]=g[0]-cost[0]\n",
    "        for i in range(1,n):\n",
    "            g[i]=g[i-1]+g[i]-cost[i]\n",
    "        if g[n-1]<0:\n",
    "            return -1\n",
    "        else:\n",
    "            return (g.index(min(g))+1)%n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        res = -1\n",
    "        for i in range(len(gas)):\n",
    "            cur_gas = 0\n",
    "            j = i\n",
    "            while True:\n",
    "                if cost[j] > cur_gas + gas[j]:\n",
    "                    break \n",
    "                cur_gas = cur_gas + gas[j] - cost[j]\n",
    "                if j >= len(gas) - 1:\n",
    "                    j = 0\n",
    "                else:\n",
    "                    j += 1\n",
    "                if j == i:\n",
    "                    res = i\n",
    "                    break\n",
    "            if res != -1:\n",
    "                return i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        start = 0\n",
    "        cur_sum = 0\n",
    "        total_sum = 0\n",
    "        for i in range(len(gas)):\n",
    "            cur_sum += gas[i] - cost[i]\n",
    "            total_sum += gas[i] - cost[i]\n",
    "            if cur_sum < 0:\n",
    "                cur_sum = 0\n",
    "                start = i + 1\n",
    "            print(start)\n",
    "        if total_sum >= 0:\n",
    "            return start\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        length = len(gas)\n",
    "        candi_gas = []\n",
    "        for i in range(length):\n",
    "            if gas[i]-cost[i] >= 0:\n",
    "                candi_gas.append(i)\n",
    "        \n",
    "        gas = gas + gas \n",
    "        cost = cost + cost\n",
    "\n",
    "        for i in candi_gas:\n",
    "            remain = 0\n",
    "            for j in range(i, i+length+1):\n",
    "                gas_now = remain + gas[j]\n",
    "                remain = gas_now-cost[j]\n",
    "                if j >= i+length:\n",
    "                    return i\n",
    "                if remain < 0:\n",
    "                    break \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        count=0\n",
    "        start=0\n",
    "        index=start\n",
    "        gas_sum=0\n",
    "        l=set()\n",
    "        while count<len(gas):\n",
    "            gas_sum+=gas[index]\n",
    "            gas_sum-=cost[index]\n",
    "            l.add(index)\n",
    "            if gas_sum<0:\n",
    "                if len(l)==len(gas):\n",
    "                    return -1\n",
    "                count=0\n",
    "                start=(index+1)%len(gas)\n",
    "                index=start\n",
    "                gas_sum=0\n",
    "                continue\n",
    "            index=(index+1)%len(gas)\n",
    "            count+=1\n",
    "        return start"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        n = len(gas)\n",
    "        gas =gas+gas\n",
    "        cost = cost+cost\n",
    "        l = [x-y for x,y in zip(gas,cost)]\n",
    "        for i in range(n):\n",
    "            oil = l[i]\n",
    "            if oil<0:continue\n",
    "            idx = i\n",
    "            while idx <=2*n:\n",
    "                if idx >= i+n:\n",
    "                    return i\n",
    "                oil += l[idx+1]\n",
    "                if oil<0:\n",
    "                    break\n",
    "                idx += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas, cost):\n",
    "        tmp = [ gas[i] - cost[i] for i in range(len(gas))]\n",
    "        prefix_sum = [tmp[0]] * len(gas) * 2\n",
    "\n",
    "        min_prefix_sum_1 = [tmp[0], 0]\n",
    "        for i in range(1, len(gas)):\n",
    "            prefix_sum[i] = prefix_sum[i-1] + tmp[i]\n",
    "            if prefix_sum[i] < min_prefix_sum_1[0]:\n",
    "                min_prefix_sum_1[0] = prefix_sum[i]\n",
    "                min_prefix_sum_1[1] = i\n",
    "\n",
    "        min_prefix_sum_2 = [float(\"inf\"), len(gas)]\n",
    "        for i in range(len(gas), 2 * len(gas)):\n",
    "            prefix_sum[i] = prefix_sum[i-1] + tmp[i - len(gas)]\n",
    "            if prefix_sum[i] < min_prefix_sum_2[0]:\n",
    "                min_prefix_sum_2[0] = prefix_sum[i]\n",
    "                min_prefix_sum_2[1] = i\n",
    "\n",
    "        print(min_prefix_sum_1,min_prefix_sum_2,prefix_sum,tmp)\n",
    "        for i in range(min_prefix_sum_1[1]+1):\n",
    "            if tmp[i] < 0:continue\n",
    "            if tmp[i] >= prefix_sum[i] - min_prefix_sum_1[0]:\n",
    "                return i\n",
    "        for i in range(min_prefix_sum_1[1]+1, len(gas)):\n",
    "            if tmp[i] >= prefix_sum[i] - min_prefix_sum_2[0]:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ListNode:\n",
    "    def __init__(self, index=0, gas=0, cost=0):\n",
    "        self.index = index\n",
    "        self.gas = gas\n",
    "        self.cost = cost\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        head = ListNode(0, gas[0], cost[0])\n",
    "        cur = head\n",
    "        for i in range(1,len(gas)):\n",
    "            node = ListNode(i, gas[i], cost[i])\n",
    "            cur.next = node\n",
    "            cur = cur.next\n",
    "        cur.next = head\n",
    "\n",
    "\n",
    "        start = head\n",
    "        left = start.gas\n",
    "        cur = start\n",
    "        timer = 0\n",
    "        while cur.next != start:\n",
    "            if left > cur.cost:\n",
    "                left = left - cur.cost + cur.next.gas\n",
    "                cur = cur.next\n",
    "                timer += 1\n",
    "            else:\n",
    "                if timer >= len(gas):\n",
    "                    return -1\n",
    "                else:\n",
    "                    cur = cur.next\n",
    "                    start = cur\n",
    "                    left = cur.gas\n",
    "                    timer += 1\n",
    "        \n",
    "        return start.index if left >= cur.cost else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        rest = 0\n",
    "\n",
    "        for i in range(len(cost)):\n",
    "            rest = gas[i] - cost[i]\n",
    "            index = (i+1) % len(cost)\n",
    "            while rest > 0 and index != i:\n",
    "                rest += gas[index]-cost[index]\n",
    "                index = (index+1) % len(cost)\n",
    "            \n",
    "            if rest >= 0 and index == i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        if sum(gas) < sum(cost):\n",
    "            return -1\n",
    "\n",
    "        index = 0\n",
    "        cur = 0\n",
    "        for i in range(len(gas)):\n",
    "            cur += gas[i] - cost[i]\n",
    "            if cur < 0:\n",
    "                cur = 0\n",
    "                index = i+1\n",
    "        return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        if sum(gas) == 0:\n",
    "            return -1\n",
    "        for i in range(len(gas)):\n",
    "            tank = gas[i]\n",
    "            lable = 1\n",
    "            if tank == 0:\n",
    "                continue\n",
    "            for j in range(1,len(gas)+1):\n",
    "                cur = (i + j)%len(gas)\n",
    "                tank -= cost[cur-1]\n",
    "                if tank < 0:\n",
    "                    lable = -1\n",
    "                    break\n",
    "                tank += gas[cur]\n",
    "            if lable == 1:\n",
    "                return i\n",
    "        return -1\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        Min = float('inf')\n",
    "        curSum = 0\n",
    "        for i in range(len(gas)):\n",
    "            curSum += gas[i] - cost[i]\n",
    "            if curSum < Min:\n",
    "                Min = curSum\n",
    "        if curSum < 0:\n",
    "            return -1\n",
    "        if Min >= 0:\n",
    "            return 0\n",
    "        for i in range(len(gas)-1, 0, -1):\n",
    "            Min += gas[i] - cost[i]\n",
    "            if Min >= 0:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        curSum = totalSum = 0\n",
    "        start = 0\n",
    "        for i in range(len(gas)):\n",
    "            tmpRest = gas[i] - cost[i]\n",
    "            curSum += tmpRest\n",
    "            totalSum += tmpRest\n",
    "            if curSum < 0:\n",
    "                curSum = 0\n",
    "                start = i + 1\n",
    "        return -1 if totalSum < 0 else start"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        #总油量 < 总耗油量，一定无解\n",
    "        if sum(gas) < sum(cost):\n",
    "            return -1\n",
    "        \n",
    "        #sum(gas) >= sum(cost)，一定有解【题目保证唯一解】\n",
    "        n = len(gas)\n",
    "        start = 0       # 记录出发点，从索引0开始\n",
    "        total = 0       # 记录汽车实际油量\n",
    "        for i in range(n):\n",
    "            total += gas[i] - cost[i]  # 每个站点加油量相当于 gas[i] - cost[i]\n",
    "            if total < 0:       # 在i处的油量<0，说明从之前站点出发的车均无法到达i\n",
    "                start = i+1     # 尝试从下一个站点i+1重新出发\n",
    "                total = 0       # 重新出发时油量置为0\n",
    "        \n",
    "        return start    # 解是唯一的\n",
    "\n",
    "        \"\"\"\n",
    "        超时方法\n",
    "        if sum(gas) < sum(cost):\n",
    "            return -1\n",
    "\n",
    "        if len(gas) == 1:\n",
    "            return 0 if gas[0]>=cost[0] else -1\n",
    "\n",
    "        for i in range(len(gas)):\n",
    "            res = [-1] * len(gas)\n",
    "            if gas[i] < cost[i]:\n",
    "                continue\n",
    "            res[i] = gas[i]\n",
    "            \n",
    "            for j in range(i+1, len(gas)):\n",
    "                if gas[j] + res[j-1] - cost[j-1] < cost[j]:\n",
    "                    break\n",
    "                else:\n",
    "                    res[j] = gas[j] + res[j-1] - cost[j-1]\n",
    "    \n",
    "            if res[-1] >= 0 and res[-1] + gas[0] - cost[-1] >= gas[0]:\n",
    "                res[0] = res[-1] + gas[0] - cost[-1]\n",
    "                for j in range(1, i):\n",
    "                    if gas[j] + res[j-1] - cost[j-1] < cost[j]:\n",
    "                        break\n",
    "                    else:\n",
    "                        res[j] = gas[j] + res[j-1] - cost[j-1]\n",
    "            if res[i-1] >= cost[i-1]:\n",
    "                return i\n",
    "\n",
    "        return -1\n",
    "        \"\"\"\n",
    "                \n",
    "                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        start=0\n",
    "        tot_sum=0\n",
    "        cur_sum=0\n",
    "        for i in range(len(gas)):\n",
    "            cur_sum+=gas[i]-cost[i]\n",
    "            tot_sum+=gas[i]-cost[i]\n",
    "            if cur_sum<0:\n",
    "                start=i+1\n",
    "                cur_sum=0\n",
    "        return -1 if tot_sum<0 else start\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        \n",
    "        '''总油量 < 总耗油量，一定无解'''\n",
    "        if sum(gas) < sum(cost):\n",
    "            return -1\n",
    "        \n",
    "        '''sum(gas) >= sum(cost)，一定有解【题目保证唯一解】'''\n",
    "        n = len(gas)\n",
    "        start = 0       # 记录出发点，从索引0开始\n",
    "        total = 0       # 记录汽车实际油量\n",
    "        for i in range(n):\n",
    "            total += gas[i] - cost[i]  # 每个站点加油量相当于 gas[i] - cost[i]\n",
    "            if total < 0:       # 在i处的油量<0，说明从之前站点出发的车均无法到达i\n",
    "                start = i+1     # 尝试从下一个站点i+1重新出发\n",
    "                total = 0       # 重新出发时油量置为0\n",
    "        \n",
    "        return start    # 解是唯一的\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        if sum(gas) < sum(cost): return -1\n",
    "        rest = []\n",
    "        for i in range(len(gas)):\n",
    "            rest.append(gas[i] - cost[i])\n",
    "        _min, _sum = 0, 0\n",
    "        for i in range(len(rest)):\n",
    "            _sum += rest[i]\n",
    "            if _sum < 0 and _min > _sum:\n",
    "                _min = _sum\n",
    "        print(_min)\n",
    "        if _min == 0: return 0\n",
    "        _sum = 0\n",
    "        for i in range(len(rest))[::-1]:\n",
    "            _sum += rest[i]\n",
    "            if _sum >= -_min:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        n=len(gas)\n",
    "        gasSurplus = 0  # 记录当前剩余油量\n",
    "        minSurplus = float('inf')   # 记录剩余油量最小值\n",
    "        indexMin = -1   # 记录剩余油量最小时的索引值\n",
    "        # 从0点出发，计算各个点的剩余油量值\n",
    "        for i in range(n):\n",
    "            gasSurplus += gas[i] - cost[i]\n",
    "            # 当比最小值小时，更新最小值（相等时也更新）\n",
    "            if gasSurplus <= minSurplus:\n",
    "                minSurplus = gasSurplus\n",
    "                indexMin = i\n",
    "        # 跑完一圈后，剩余油量若为负，则意味着一圈的总消耗大于总补给，不可能跑完一圈\n",
    "        if gasSurplus < 0:\n",
    "            return -1\n",
    "        return (indexMin+1)%n \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        station_len = len(gas)\n",
    "        start_pos = 0\n",
    "        while start_pos < station_len:\n",
    "            finish = True\n",
    "            temp = 0\n",
    "            for i in range(start_pos, start_pos + station_len):\n",
    "                temp += (gas[i%station_len]-cost[i%station_len])\n",
    "                if temp<0:\n",
    "                    start_pos = i+1\n",
    "                    finish = False\n",
    "                    break\n",
    "            if finish:\n",
    "                return start_pos\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        start = 0\n",
    "        allgas = 0\n",
    "        rest = 0\n",
    "        for i in range(len(gas)):\n",
    "            allgas += gas[i] - cost[i]\n",
    "            rest += gas[i] - cost[i]\n",
    "            if allgas < 0:\n",
    "                start = i + 1\n",
    "                allgas = 0\n",
    "        return -1 if rest < 0 else start"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        if sum(gas) < sum(cost):\n",
    "            return -1\n",
    "        total, start = 0, 0\n",
    "        for i in range(len(gas)):\n",
    "            total += gas[i] - cost[i]\n",
    "            if total < 0:\n",
    "                start = (i + 1) % len(gas)\n",
    "                total = 0\n",
    "        return start"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        \n",
    "        stackgas = 0\n",
    "        mingas = float('inf')\n",
    "\n",
    "        for i in range(len(gas)):\n",
    "            res = gas[i] - cost[i]\n",
    "            stackgas += res\n",
    "            # if stackgas < mingas:\n",
    "            #     mingas = stackgas\n",
    "\n",
    "            mingas = min(stackgas, mingas)\n",
    "\n",
    "        if stackgas < 0:\n",
    "            return -1\n",
    "\n",
    "        if mingas >= 0:\n",
    "            return 0\n",
    "\n",
    "        for i in range(len(gas)-1, -1, -1):\n",
    "            res = gas[i] - cost[i]\n",
    "            mingas += res\n",
    "            if mingas >= 0:\n",
    "                return i\n",
    "        \n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "#         for i in range(len(gas)):\n",
    "#             if gas[i] < cost[i]:\n",
    "#                 continue\n",
    "#             j = i-1\n",
    "#             start = 0\n",
    "#             res = gas[i]\n",
    "#             while j != i:\n",
    "#                 if start == 0:\n",
    "#                     j = i\n",
    "#                 if j + 1 < len(gas):\n",
    "#                     res = res - cost[j] + gas[j+1]\n",
    "#                     if res >= cost[j+1]:\n",
    "#                         j += 1\n",
    "#                     else:\n",
    "#                         break\n",
    "#                 else:\n",
    "#                     if j == len(gas)-1:\n",
    "#                         j = -1\n",
    "#                     res = res - cost[j] + gas[j+1]\n",
    "#                     if res >= cost[j+1]:\n",
    "#                         j += 1\n",
    "#                     else:\n",
    "#                         break\n",
    "#                 start += 1\n",
    "            \n",
    "#             if start == len(gas):\n",
    "#                 return i\n",
    "\n",
    "#         return -1\n",
    "\n",
    "# class Solution:\n",
    "#     def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "#         for i in range(len(cost)):\n",
    "#             rest = gas[i] - cost[i]  # 记录剩余油量\n",
    "#             index = (i + 1) % len(cost)  # 下一个加油站的索引\n",
    "\n",
    "#             while rest > 0 and index != i:  # 模拟以i为起点行驶一圈（如果有rest==0，那么答案就不唯一了）\n",
    "#                 rest += gas[index] - cost[index]  # 更新剩余油量\n",
    "#                 index = (index + 1) % len(cost)  # 更新下一个加油站的索引\n",
    "\n",
    "#             if rest >= 0 and index == i:  # 如果以i为起点跑一圈，剩余油量>=0，并且回到起始位置\n",
    "#                 return i  # 返回起始位置i\n",
    "\n",
    "#         return -1  # 所有起始位置都无法环绕一圈，返回-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        if sum(cost)>sum(gas):\n",
    "            return -1\n",
    "        n=len(cost)\n",
    "        g=[gas[i]-cost[i] for i in range(n)]\n",
    "        stack=[]\n",
    "        ans=0\n",
    "        total_gas=0\n",
    "        i=0\n",
    "        while i<2*n:\n",
    "            total_gas+=g[i%n]\n",
    "            if total_gas<0:\n",
    "                if i>=n:\n",
    "                    return -1\n",
    "                total_gas=0\n",
    "                ans=i+1\n",
    "            i+=1        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        for i in range(len(gas)):\n",
    "            gas[i] = gas[i] -cost[i]  #gas 加油  cast 耗油\n",
    "        if sum(gas) < 0:\n",
    "            return  -1\n",
    "        start = 0\n",
    "        sum1 = 0\n",
    "        for i in range(len(gas)):\n",
    "            sum1 += gas[i]\n",
    "            if sum1 < 0:\n",
    "                sum1 = 0 # 归零，从当前位置开始\n",
    "                start =  i+1\n",
    "        return start\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        left = [gas[i] - cost[i] for i in range(len(gas))]\n",
    "        minValue = 999\n",
    "        minIndex = 0\n",
    "\n",
    "        sumValue = 0\n",
    "        for j, l in enumerate(left):\n",
    "            sumValue += l\n",
    "            if sumValue <= minValue:\n",
    "                minValue = sumValue\n",
    "                minIndex = j\n",
    "        \n",
    "        if sumValue < 0:\n",
    "            return -1\n",
    "        else:\n",
    "            return (minIndex + 1) % len(gas)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "\n",
    "        dif = [0]*len(gas)\n",
    "        for i in range(len(gas)):\n",
    "            dif[i] = gas[i]-cost[i]\n",
    "\n",
    "        i = 0\n",
    "        while i < len(gas):\n",
    "            count = 0\n",
    "            now_gas = 0\n",
    "            while count<len(gas):\n",
    "                now = (count+i+len(gas))%len(gas)\n",
    "                now_gas += dif[now]\n",
    "                \n",
    "                if now_gas>=0:\n",
    "                    count+=1\n",
    "                else:\n",
    "                    break\n",
    "                    \n",
    "            if count==len(gas):\n",
    "                return i\n",
    "            elif count<len(gas):\n",
    "                i = i+count+1\n",
    "\n",
    "                    \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        length = len(gas)\n",
    "\n",
    "        current_gas = 0\n",
    "        current_start_index = None\n",
    "\n",
    "        for i in range(0, length * 2 -1):\n",
    "            if i < length:\n",
    "                gas[i] = gas[i] - cost[i]\n",
    "                gas.append(gas[i])\n",
    "\n",
    "            if current_start_index is not None and i - current_start_index + 1 > length:\n",
    "                break\n",
    "\n",
    "            current_gas += gas[i]\n",
    "            if current_gas < 0:\n",
    "                current_start_index = None\n",
    "                current_gas = 0\n",
    "            else:\n",
    "                if current_start_index is None:\n",
    "                    current_start_index = i\n",
    "\n",
    "        if current_start_index is None or current_start_index >= length:\n",
    "            return -1\n",
    "        return current_start_index\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        start=0\n",
    "        end=0\n",
    "        gas+=gas\n",
    "        cost+=cost\n",
    "        n=len(gas)//2\n",
    "        cur_gas=0\n",
    "        total_gas=0\n",
    "        if sum(cost)-sum(gas)>0:\n",
    "            return -1            \n",
    "        for i in range(n):\n",
    "            cur_gas+=gas[i]-cost[i]\n",
    "            total_gas+=gas[i]-cost[i]            \n",
    "            if cur_gas<0:\n",
    "                start=i+1\n",
    "                end=min(start+n,len(gas))\n",
    "                tank=0\n",
    "                for s in range(start,end):\n",
    "                    tank+=gas[s]-cost[s]\n",
    "                    if tank<0:\n",
    "                        break\n",
    "                if tank>=0:\n",
    "                    return start\n",
    "        if start>=n:\n",
    "            start-=n\n",
    "        return start"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        if sum(gas) < sum(cost):\n",
    "            return -1\n",
    "        \n",
    "        n = len(gas)\n",
    "        for i in range(n):\n",
    "            cost[i] = gas[i] - cost[i]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            cost[i] += cost[i+1]\n",
    "        ret, g = 0, cost[0]\n",
    "        for i in range(1, n):\n",
    "            if cost[i] > g:\n",
    "                g = cost[i]\n",
    "                ret = i\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\r\n",
    "        '''\r\n",
    "        start = 0\r\n",
    "        current_sum = 0\r\n",
    "        total_sum = 0\r\n",
    "\r\n",
    "        for i in range(len(gas)):\r\n",
    "            current_sum = current_sum + gas[i] - cost[i]\r\n",
    "            total_sum = total_sum + gas[i] - cost[i]\r\n",
    "\r\n",
    "            if current_sum < 0:\r\n",
    "                current_sum = 0\r\n",
    "                start = i + 1\r\n",
    "        \r\n",
    "        if total_sum < 0:\r\n",
    "            return -1\r\n",
    "        \r\n",
    "        return start\r\n",
    "        '''\r\n",
    "\r\n",
    "        if sum(gas) - sum(cost) < 0:\r\n",
    "            return -1\r\n",
    "        \r\n",
    "        lvpi_31 = [0]\r\n",
    "\r\n",
    "        for i in range(0, len(gas) - 1):\r\n",
    "            lvpi_31.append(lvpi_31[-1] + gas[i] - cost[i])\r\n",
    "        \r\n",
    "        lowest_measurement = min(lvpi_31)\r\n",
    "\r\n",
    "        for i in range(len(lvpi_31)):\r\n",
    "            if lvpi_31[i] == lowest_measurement:\r\n",
    "                return i"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
